package ext;

import java.util.Date;

import org.junit.Test;

import util.BracketUtils;

public class PathGet {
    class Solution {
        public int minPathSum(int[][] nums) {    
            int m = nums.length, n = nums[0].length;
            int[][] f = new int[m][n];
            int[][][] path = new int[m][n][2];
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    if (i == m - 1 && j == n - 1) {
                        f[i][j] = nums[i][j];
                    } else if (i == m - 1) {
                        //上一轮只可能从右边来
                        f[i][j] = f[i][j + 1] + nums[i][j];
                        path[i][j] = new int[]{i, j + 1};
                    } else if (j == n - 1) {
                         //上一轮只可能从下边来
                        f[i][j] = f[i + 1][j] + nums[i][j];
                        path[i][j] = new int[]{i + 1, j};
                    } else {
                        if (f[i + 1][j] >= f[i][j + 1]) {
                            f[i][j] = f[i][j + 1] + nums[i][j];
                            path[i][j] = new int[]{i, j + 1};
                        } else {
                            f[i][j] = f[i + 1][j] + nums[i][j];
                            path[i][j] = new int[]{i + 1, j};
                        }
                    }
                }
            }
    
            // 再来一轮，得到所有的路径
            int i = 0, j = 0, idx=0;
            while (!(i == m - 1 && j == n - 1)) {
                int[] cur = path[i][j];
                i = cur[0];
                j = cur[1];
                System.out.printf("第%d轮选择了(%d, %d)\n", idx++, i, j);
            }
    
            // System.out.printf("第%d轮选择了(%d, %d)", idx++, i, j);     
            return f[0][0];
        }
    }

    @Test
    public void test() {
        // Solution s = new Solution();
        // int[][] nums = BracketUtils.to2DArray("[[1,3,1],[1,5,1],[4,2,1]]");
        // System.out.println(s.minPathSum(nums));
        System.out.println(new Date(1639951200000L));

    }
}
